package com.demo.study.algorithm.leetcode;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * LT383
 * <a href="https://leetcode.cn/problems/ransom-note/">赎金信</a>
 *
 * @author Baymax
 * @since 2024-11-15
 */
public class LT383 {
    @Test
    public void run() {
        System.out.println(canConstruct2("aa", "ab"));
    }

    public boolean canConstruct(String ransomNote, String magazine) {
        char[] charArray = magazine.toCharArray();
        List<String> list = new ArrayList<>();
        for (char c : charArray) {
            list.add(String.valueOf(c));
        }
        boolean flag = true;
        for (char charStr : ransomNote.toCharArray()) {
            String str = String.valueOf(charStr);
            boolean result = list.remove(str);
            if (!result) {
                flag = false;
            }
        }
        return flag;
    }

    public boolean canConstruct1(String ransomNote, String magazine) {
        boolean flag = true;
        for (char ranChar : ransomNote.toCharArray()) {
            if (!magazine.contains(String.valueOf(ranChar))) {
                flag = false;
                break;
            }
            magazine = magazine.replaceFirst(ranChar + "", "");
        }
        return flag;
    }

    public boolean canConstruct2(String ransomNote, String magazine) {
        for (char ranChar : magazine.toCharArray()) {
            ransomNote = ransomNote.replaceFirst(ranChar + "", "");
        }
        return ransomNote.isEmpty();
    }

    public boolean canConstruct3(String ransomNote, String magazine) {
        int[] arr = new int[26];
        for (int i = 0; i < magazine.length(); ++i) {
            arr[magazine.charAt(i) - 97]++;
        }
        for (int i = 0; i < ransomNote.length(); ++i) {
            arr[ransomNote.charAt(i) - 97]--;
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < 0) {
                return false;
            }
        }
        return true;
    }


}
